1. Field of the Invention
This invention relates to a method of routing packets of information over paths between source and destination nodes in an information network.
2. Discussion of the Known Art
Today""s Internet incorporates so-called xe2x80x9cbest effortxe2x80x9d routing. That is, a source node in the network is connected to a destination (sink) node over a path of network links, using protocols that do not always assure a given level of service quality. For example, given the dynamic nature of Internet traffic, it is possible (and presently permitted) that packets will encounter unexpected delays. While best effort routing has been adequate for traditional applications such as File Transfer Protocol (FTP), modern applications such as real-time audio or video require strict routing performance guarantees for satisfactory transmission via the Internet.
It is contemplated that the Internet will eventually have to support various levels of quality of service (QoS) in addition to a xe2x80x9cbest effortxe2x80x9d one. For example, each level may have its own set of service guarantees, and packets associated with certain applications may be favored over others so as to satisfy a given performance requirement for such applications. Accordingly, users of these applications may be charged more than users of applications having less stringent transmission requirements.
Several proposals have been advanced to support various forms of guaranteed service classes. See, e.g., R. Braden, et al, Integrated Services in the Internet Architecturexe2x80x94An Overview, RFC 1633; and Differentiated Service for the Internet, URL=diffserv.lcs.mit.edu. A core component of these proposals is the identification of a routing path for an application based on (1) QoS requirements for the application, and (2) available resources of the network.
The QoS requirements of an application are specified as either a set of path-constraints, i.e., requirements on an entire path between source and sink nodes in a network, or a set of link-constraints, i.e., requirements on individual network links that form a given path. See W. Lee, et al, Routing Subject to Quality of Service Constraints in Integrated Communication Networks, IEEE Networks (July 1995); and R. Nagarajan, et al, Allocation of Local Quality of Service Constraints to Meet End-to-End Requirements, IFIP Workshop on the Performance Analysts of ATM Systems (1993). A path with sufficient network resources to satisfy the QoS requirements of a given application is called a feasible path. Further, one or more optimization criteria may then narrow a selection among the feasible paths. A goal of QoS routing then becomes finding the optimal feasible path. See E. Crawley, et al: A Framework for QoS-Based Routing in the Internet, RFC 2386 (August 1998).
In addition to improving the performance of individual applications, QoS routing may improve overall network efficiency. See G. Apostolpoulos, et al, Quality of Service Routingxe2x80x94A Performance Perspective, ACM Sigcomm (1998); Z. Wang, et al, Quality of Service Routing for Supporting Multi-Media Applications, IEEE Journal on Selected Areas in Communications, 14(7) at 1228-1234 (1996); and W. Lee, et al, supra. Such gains must be weighed carefully against the complexity and cost of implementing the required QoS routing algorithms in a given network, however. Unfortunately, most QoS problems belong in a class called xe2x80x9cmulti-objective optimizationxe2x80x9d, which tends to be NP (nondeterministic polynomial time)-hard. Thus, past efforts have concentrated on finding various heuristics, i.e., sub-optimal algorithms often lacking any performance guarantees, or algorithms guaranteed to be optimal only for certain special cases.
Consider a network of n nodes and m links, wherein each link has an associated cost function ce(d) representing a cost incurred by guaranteeing a delay of not more than d on link e. For a given source node s and a destination node t, an end-to-end delay constraint of D needs to be satisfied. The following two problems then arise:
1. Constrained minimum cost path (PATH): Find a path in the network from s to t, and determine how much to pay for each link of the path, in order that (a) the total delay over the path is not more than D, and (b) the total cost for all links of the path is minimized. p1 2. Constrained minimum cost partition (PARTITION): Assume a feasible s-t path P of p links has been determined. Then determine how much to pay on each link of the path in order to (a) maintain the total delay constraint D, and (b) minimize the total cost for all links.
PARTITION thus maps a path constraint of PATH into link constraints. PATH is also a generalization of the so-called restricted shortest path problem (RSP), in which each link has one fixed cost ce with fixed delay de. Both PATH and PARTITION may be solved optimally with dynamic programming. See R. Guerin, et al, QoS Based Routing in Networks With Inaccurate Information, IEEE/ACM Transactions on Networking, at 350-364 (June 1999). The running time 0(D2m) is pseudo-polynomial, however. The RSP, a special case of PATH, is also NP-hard.
Approximation techniques have been given for solving RSP. See R. Hassin, Approximation Schemes for the Restricted Shortest Path Problem, Mathematics of Operations Research, 17(1) at 36-42 (February 1992)(hereafter xe2x80x9cHassinxe2x80x9d), which is incorporated by reference. Hassin uses a technique called xe2x80x9crounding-and-scalingxe2x80x9d to solve RSP, wherein a set of possible delay values are xe2x80x9cscaledxe2x80x9d down to a small enough range so that the scaled problem may be solved optimally in polynomial time. The solution is then xe2x80x9croundedxe2x80x9d back to the original delay values with some bounded error.
Throughout prior studies, cost functions for each link are assumed to be convex. In D. Lorenz, QoS Routing, supra, a xe2x80x9cgreedyxe2x80x9d approach is disclosed for obtaining optimal solutions, as well as a polynomial time xcex5-approximation.
Generally, when running an xcex5-approximation procedure, a value (typically 0 less than xcex5 less than 1) is chosen which corresponds to how xe2x80x9cclosexe2x80x9d an approximation is desired. For example, if the approximation result is to be 90% accurate, xcex5 is chosen so that 1/(1+xcex5)=0.9, or xcex5≈0.1. The smaller the value of xcex5, the more accurate the approximation but the longer it takes to run the procedure.
Variants of the greedy approach for PARTITION with improved polynomial running time are disclosed in D. Lorenz, et al, Optimal Partition of QoS Requirements on Unicast Paths and Multicast Trees, IEEE Infocom (1999).
According to the invention, a method of determining an optimal path from a source node to a destination node over a number of links in an information network having n nodes, wherein each link has an associated cost-delay function, the optimal path is constrained to an overall delay of D, and a total cost of all links along the path is minimized at a value OPT, includes maintaining a range [L, U] for OPT, wherein L is a lower bound and U is an upper bound, setting initial values of L and U, setting a cost value V corresponding to {square root over (Uxc2x7L)}, and scaling a known cost c of each link from c to cxe2x80x2, wherein cxe2x80x2 corresponds to cn/Vxcex5, and xcex5 greater than 0.
The method also includes determining if a feasible path exists having a delay of at most D and a total cost of at most V and, if no feasible path exists, then increasing the value of L and returning to the cost value setting and the link cost scaling steps, decreasing the value of U and continuing to increase the value of L until U/L less than 2 and a feasible path continues to exist, and identifying the links of the feasible path as the optimal path.